public class Solution377 {
    public int combinationSum4(int[] nums, int target) {
        int[][] dp=new int[target+1][target+1];
        dp[0][0]=1;
        for (int i = 0; i < target; i++) {
            int[] lastDP=dp[i];
            int[] tmpDP=dp[i+1];
            for (int j = 0; j < target+1; j++) {
                int tmpNum=lastDP[j];
                for (int k = 0; k < nums.length; k++) {
                    int loc=j+nums[k];
                    if(loc<=target)
                        tmpDP[loc]+=tmpNum;
                }
            }
        }

        int sum=0;
        for (int i = 0; i <= target; i++) {
            sum+=dp[i][target];
        }
        return sum;
    }


    public static void main(String[] args) {
        Solution377 s=new Solution377();
        System.out.println(s.combinationSum4(new int[]{1,2,3},4));
    }
}
